The present invention relates generally to an algorithm for solving resource optimization problems within computer systems. More specifically, the present invention relates to a method and an apparatus that uses resource allocation techniques derived from a financial market model to solve a multi-objective sensor based network optimization problem.
As technology reaches into every aspect of modern human life, we find that huge sensor networks are deployed across large geographic areas and even across the globe. Such sensor-based networks actively detect information that is in turn processed and utilized to deploy and/or control various resource devices that are attributed to and controlled by the network. In enhancing and controlling the overall operation of such a sensor-based network, there are often several competing objectives that one would like to optimize. The difficulty arises in that rarely is it possible to optimize such a network in a manner wherein the optimization of each of the various competing objectives coincides. As a result, the control system is often left with tradeoff solutions that represent a compromise solution that exists between the individual objectives. Ultimately, it is this compromise solution that must be incorporated into the final control solution. The goal therefore in solving such an optimization problem that has a multi-objective structure is to determine a set of points that describe the optimal or most efficient trade-offs between the competing objectives.
The above-identified problem, however, becomes more complex as the overall structure of the network increases in scale. As the number of sensor inputs or resources available on the network increase, the system itself becomes highly dynamic and the complexity of the optimization process itself increases dramatically making it quite likely that large errors and inefficient resource allocations result. In a very simplistic example, feedback control systems are widely used to maintain the output of a dynamic system at a desired value in spite of external disturbance forces that would move the output away from the desired value. In this context, a household furnace controlled by a thermostat is an example of a feedback control system. The thermostat continuously measures the air temperature of the house, and when the temperature falls below a desired minimum temperature, the thermostat turns the furnace on. When the furnace has warmed the air above the desired minimum temperature, the thermostat then turns the furnace off. The thermostat-furnace system maintains the household temperature at a constant value in spite of external disturbances such as a drop in the outside air temperature. Similar types of feedback control are used in many applications.
While a simple control loop may work in the above noted example, as systems become more complex, these simple on-off feedback controls are insufficient. More advanced control systems rely on combinations of proportional feedback control, integral feedback control, and derivative feedback control. Feedback that is the sum of proportional plus the integral plus the derivative feedback is often referred to in the context of PID control. Even in these control systems, however, the network system parameters are assumed to be relatively linear, time invariant and stable. Accordingly, the base assumptions in a PID control system create a problem in attempting to optimize systems that have sensor inputs that are time varying, highly nonlinear, and unstable. For example, the system depicted in the dynamic model may contain parameters that are either poorly known or depend on a changing environment. If the parameter variation is small and the dynamic model is stable, then the PID controller may be sufficient. However, if the parameter variation is large, or if the dynamic model is unstable, then it is necessary to add adaptation or intelligent (AI) control to the PID control system.
In any case, evaluating the resource allocation characteristics of a nonlinear or highly dynamic system is often difficult, in part due to the lack of a general analysis method. The trade off when controlling such a system is to find certain equilibrium points in the operation of the system and linearize those characteristics at or around the equilibrium points. Optimization is then based on evaluating the pseudo (linearized) characteristics near the equilibrium point. This technique works poorly, if at all, for complex systems described by models that are unstable or dissipative.
Therefore, there is a need for an algorithm that allows optimization of the resources on a complex and highly dynamic sensor based network. There is a further need of an algorithm that facilitates the optimization of a highly dynamic sensor based network that evaluates the whole world of possible allocations of the resources available on the network and makes a global determination of the most efficient allocation of those resources despite the existence of local or regionalized allocation loops.